# LeetCode 210、课程表II
# 一、题目描述
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
- 例如，想要学习课程
0，你需要先完成课程1，我们用一个匹配来表示：[0,1]。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi- 所有
[ai, bi]互不相同
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 课程表II（LeetCode 210）：https://leetcode.cn/problems/course-schedule-ii/
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 1、记录每一个课程的情况
// 即，记录课程号与课程前置课程数量
// 使用哈希表来记录，可以快速获取和新增结果
// 在图这种数据结构里面专业术语叫做记录每个课程的【入度】
// key: 课号
// value: 学习这门课程的前置课程数量
Map<Integer,Integer > inDegree = new HashMap<>();
// 2、初始化哈希表
for (int i = 0 ; i < numCourses ;i++) {
// 3、每个课程的前置课程默认都是 0
inDegree.put(i , 0);
}
// 4、记录每个课程之间的依赖关系
// 从而知道完成某个课程的时候，其它哪些课程被影响到了
// 由于被影响的课程可能有很多个，所以采用数组的形式保存被影响的那些课程
// 依赖关系，在图这种数据结构里面专业术语叫做邻接表
// key: 课号
// value: 依赖这门课的后续课，涉及多门，数组保存
Map<Integer ,List<Integer>> map = new HashMap<>();
// 5、遍历 prerequisites 数组
// 更新 inDegree 与 map
for (int[] arr : prerequisites) {
// prerequisites 数组中的每一个元素都是数组的形式
// 每一个元素记录了两个数据
// [first , second ]
// 学 first 的前置课程之一是完成 second
// 完成 second 会影响 first 的前置课程数量
int first = arr[0];
int second = arr[1];
// 6、更新入度
// 即更新 first 的前置课程数量，加 1 操作
inDegree.put( first , inDegree.get(first) + 1 );
// 7、更新依赖
// 即记录 second 会影响哪些课程
// 此时 ， second 必然会影响 first
if (!map.containsKey(second)) {
map.put(second ,new ArrayList<>());
}
// 8、更新 second 影响的课程
map.get(second).add(first);
}
// 9、开始去选修课程，只有没有前置课程的课程才能去选修
// 即入度为 0 的课程才能去选修
// 完成了一个入度为 0 的课程之后，会影响它的后续课，如果后续课为 0 了，又能选修了
// 以此类推
// 一开始把所有入度为 0 的课程都加入到队列里面
Queue<Integer> q = new LinkedList<>();
//result
List<Integer> result = new ArrayList<>();
for (int key : inDegree.keySet()) {
if (inDegree.get(key) == 0) {
q.offer(key);
result.add(key);
}
}
// 10、每个课程依次出列进行处理
// a、减小相关课的入度
// b、如果相关课的入度变为 0，也可以加入到队列里面
// 直到队列为空，即没有课程可以选修为止
while (!q.isEmpty()) {
// 课程出队
int course = q.poll();
// System.out.println(course);
// 如果发现该课程不会对任何一个课程有影响
// 即，如果发现依赖关系（邻接表）没有 course
// 那么直接去查看下一个课程的情况
if (!map.containsKey(course)) {
continue;
}
// 否则开始更新当前课程的所有后续课程的【入度】情况
// 获取当前课程的所有的后续课程
List<Integer> successorList = map.get(course);
// 更新后续课程的【入度】情况
for (int k : successorList) {
// 当前课程 course 选修完毕之后
// 每个后续课程的前置课程数量减一
// 即【入度】减一
inDegree.put( k ,inDegree.get(k) - 1);
// 如果发现后续某个课程【入度】为零
if (inDegree.get(k) == 0) {
// 把它也加入到队列处理
q.offer(k);
result.add(k);
}
}
}
// 11、由于只有入度为零的课程才能被选修
// 因此，遍历 inDegree，查看是否还有入度为非零的课程
for (int key : inDegree.keySet()) {
// 如果有，说明当前课程无法被选修
if ( inDegree.get(key) != 0 ) {
// 即无法完成所有课程的学习，返回 一个空数组
return new int[]{};
}
}
// 12、否则说明可以完成所有课程的学习，返回 任意一种 顺序
return result.stream().mapToInt(Integer::valueOf).toArray();
}
}